package promote.brozen.algorithm.leetcode._64;

/**
 * @author Brozen
 * @date 2020/10/9 8:34 PM
 * @email brozen@qq.com
 */
public class MinPathSum {

    /**
     * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
     *
     * 说明：每次只能向下或者向右移动一步。
     *
     * 示例:
     *
     * 输入:
     * [
     *   [1,3,1],
     *   [1,5,1],
     *   [4,2,1]
     * ]
     * 输出: 7
     * 解释: 因为路径 1→3→1→1→1 的总和最小。
     */
    public int minPathSum(int[][] grid) {

        int m = grid.length;
        if (m <= 0) {
            return 0;
        }

        int n = grid[0].length;
        if (n <= 0) {
            return 0;
        }

        int[][] result = new int[n][m];
        int len = 0;
        for (int i = 0; i < m; i++) {
            result[0][i] = len += grid[i][0];
        }
        len = 0;
        for (int i = 0; i < n; i++) {
            result[i][0] = len += grid[0][i];
        }

        for (int y = 1; y < m; y++) {
            for (int x = 1; x < n; x++) {
                int a = result[x-1][y];
                int b = result[x][y-1];
                if (a > b) {
                    result[x][y] = grid[y][x] + b;
                } else {
                    result[x][y] = grid[y][x] + a;
                }
            }
        }

        return result[n-1][m-1];
    }

}
